Setelah Fenomena terjual sebanyak 200,000 salinan di Malaysia dan 700,000 salinan di Indonesia pada tahun 1989, Search telah memenangi Anugerah Juara Lagu '89 dengan lagu "Isabella" dan juga mendapat anugerah Penyanyi Berkumpulan Popular oleh Berita Harian. Mereka juga telah diundang untuk berlakon dalam filem Fenomena dan Isabella. Oleh sebab itu, ramai yang menantikan album mereka yang seterusnya.

Akhirnya pada tahun 1990, Search telah mengumumkan bahawa mereka akan merakamkan Karisma dan menggunakan khidmat M. Nasir sebagai penerbit dan komposer. Untuk album ini, Search telah memfokuskan pada susunan muzik yang lebih berat dan dinamik terutamanya dari segi 'riff' dan 'sound' seperti "Melastik ke Bintang" dan "Dunia Milik Kita". Berlainan dengan album sebelum ini, terdapat hanya dua lagu balada sahaja di dalam album ini, iaitu "Teguh" dan "Sutera atau Rayon". Search berharap agar dengan keluarnya album ini, maka dapat menyedarkan pengkritik yang mendakwa 'sound' Search menjadi berbeza selepas Hillary Ang keluar. Dalam proses rakaman tersebut, hanya 11 daripada 14 lagu sahaja yang dipilih untuk album ini. Pada awalnya, album ini sepatutnya mengandungi dua lagi lagu bahasa Inggeris tetapi tidak berjaya.[1]

Album ini merupakan album pertama yang menggunakan sistem rakaman DDD, di mana semua rakaman, mastering dan adunan dilakukan dalam pita rakaman digital. Hal ini menjadikan bunyi album ini lebih jelas dan mudah didengari.

Search pada mulanya telah merancang untuk menggunakan nama Melastik ke Bintang. Dengan merasakan nama Karisma adalah lebih baik, mereka menggunakan Karisma sebagai tajuk album.